Remember

Remembering Ken Iverson

   by Roger Hui, November 2004

Acknowledgments

I am indebted to Chris Burke, Eric Iverson, Eugene McDonnell,
Donald McIntyre, Roland Pesch, Joey Tuttle, and Arthur Whitney
for reading earlier drafts of the paper.

0. Beginnings

I first met Ken Iverson early in 1981 in Toronto, when he invited me
to dinner, along with Mrs. Jean Iverson, and Eugene McDonnell, Lib Gibson,
David Keith, and Jane Minett of I.P. Sharp Associates.
I believe the dinner happened because Eugene mentioned
me to Ken, mainly due to The N Queens Problem paper
[0]
I had submitted to the Recreational APL column that he wrote and edited.

So now not only was I to meet the great Ken Iverson,
inventor of APL, but I was also to get a free dinner.
The latter was a consideration: at the time
I was a graduate student at the University of Toronto.
At the appointed hour I went up to Ken’s apartment on the
47th floor of the Manulife Center.
I was so in awe of the great man that I took scant notice of
the spectacular view—from the apartment one can see Niagara Falls,
a 90 minute drive away—until Ken directed me to do so.

We then went for dinner at a restaurant on King Street.
I don’t remember much about the dinner,
except for the way Ken left the tip.
The change came back from paying the dinner check, in the form of
the dingiest looking bills you ever saw. Ken took out his wallet,
extracted some crisp clean bills, and crumbled them up before
leaving them on the tray.

In another sense, I had “met” Ken Iverson years before,
when I learned APL during my undergraduate studies
at the University of Alberta, from reading the
APL360 User’s Manual
[1]
and from working at the computer terminal.
Since I did not have direct access to Ken,
I read his papers carefully, principally
The Design of APL
[2],
The Evolution of APL
[3], and
Notation as a Tool of Thought
[4].
I also further acquainted myself with APL
during the summers of 1975 and 1976,
when Lib Gibson hired me to work as a summer student
at I.P. Sharp in Calgary.

1. From APL to J

The late 70’s and early 80’s were an exciting time for APL.
APL was a commercial success. APL was taught in schools and
universities. APL conferences were well-attended.
(I attended my first APL conference in 1979 in Rochester,
and my recollected impression
is that the parallel sessions at the conference each had audiences
of over a hundred.)

Ken had published his seminal paper Operators and Functions
[5]
in April 1978.
He went from IBM to I.P. Sharp in Toronto in 1980,
and there collaborated with Arthur Whitney on
Practical Uses of a Model of APL
[6]
in 1981-82, leading to Rationalized APL
[7]
in January 1983, multiple editions of
A Dictionary of the APL Language between 1984 and 1987,
and A Dictionary of APL
[8]
in September 1987. Within I.P. Sharp,
the phrase “dictionary APL” came into use to denote the APL
specified by A Dictionary of APL, itself referred
to as “the dictionary”.

At that time, the main APL vendors were IBM, STSC,
and I.P. Sharp, and all were active in developing and
extending the language.
IBM had APL2, based on the work of Trenchard More and Jim Brown
[9,
10,
11].
Work on APL2 proceeded intermittently for 15 years
[12],
with actual coding starting in 1971 and
APL2 becoming available as an IUP in 1982.
STSC had an experimental APL implementation called NARS
[13].
NARS and APL2 differed in fundamental respects
from dictionary APL (and differed from each other).

I.P. Sharp implemented the new APL ideas in stages,
complex numbers, enclosed (boxed) arrays, match, and composition operators
(on, over, under) in 1981
[14,
15],
determinant in 1982
[16],
and the rank operator, lev (left),
dex (right), and link in 1983
[17].
However, the domains of operators
were restricted to the primitive functions or subsets thereof.
I.P. Sharp also had SHARP APL/HP
[18],
principally the work of Arthur Whitney with the
assistance of Rob Hodgkinson.

An important stepping stone from APL to J was SAX
[19],
SHARP APL/Unix, written in C and based on an implementation by STSC.
An alpha version of SAX became available within I.P. Sharp
around December 1986 or early 1987. From that time to August 1989,
when the first J source line was written,
I had access to SAX, and in the later part of that period
used SAX on a daily basis.

SAX implemented dictionary APL in part,
and was upward-compatible with mainframe SHARP APL in order
to run applications ported from there.
It permitted derived or user-defined functions
as arguments to operators, and
had the special APL characters, workspaces, and the
del-form function definition.
However, it did not permit functions and operators to be named
using the assignment arrow, as in the
phrase sum←+/ ,
precluding what later came to be called tacit definition.
(The dictionary specified such assignment.)
It also did not have hooks and forks
[20],
for those were not yet invented.
For Ken, an important drawback to SAX was that
it was not widely and freely available.

From a personal perspective,
another important stepping stone from APL to J was the writing
of my APL87 paper Some Uses of { and }
[21].
At the time both Ken and I were working for I.P. Sharp
in Toronto, and the ideas in the paper evolved over many
conversations with Ken. Writing the paper refined and sharpened
my understanding of dictionary APL.

Arthur Whitney, from collaborating with Ken on
Practical Uses of a Model of APL
[6]
in 1981-82,
inventing the rank operator while on the train ride to
the APL82 conference in Heidelberg in 1982
[22,
23],
and implementing SHARP APL/HP in 1986
[18],
went on to Morgan Stanley in 1988 and there invented A
[24].
He later invented k
[25]
in 1993 and q
[26]
in 2003.
(Arthur is a classmate from the University of Alberta;
over the years our paths have crossed many times,
and each time I had benefitted.
But that is a story for another time.)

In the wider world, the PC revolution was in full swing.
It was now possible to have a computer (for example,
the AT&T 3B1 UNIX PC or
the IBM PC/AT) at home that was
a reasonable platform for developing an APL system.
Not too long ago, such a platform would be under lock and key
in a room with a raised floor,
inaccessible to mere mortals and not readily available
for experimentation.

The conditions were ripe for …

2. J

The story of how J began has been told in detail by Donald McIntyre
[27].
Ken himself wrote in A Personal View of APL
[28]:

Work began in the summer of 1989 when I first discussed my desires
with Arthur Whitney. He proposed the use of C for implementation,
and produced (on one page and in one afternoon)
a working fragment that provided only one function (+),
one operator (/), one-letter names,
and arrays limited to ranks 0 and 1, but did provide
for boxed arrays and for the use of the copula for assigning names
to any entity.

I showed this fragment to others in the hope of interesting someone
competent in both C and APL to take up the work, and soon recruited
Roger Hui, who was attracted in part by the unusual style of C
programming used by Arthur, a style that made heavy use of preprocessing
facilities to permit writing further C in a distinctly APL style.

Roger and I then began collaboration on the design and implementation
of a dialect of APL (later named J by Roger), first deciding to roughly
follow “A Dictionary of APL” and to impose no requirement of
compatibility with any existing dialect. We were assisted by suggestions
from many sources, particularly in the design of the spelling scheme
(E.B. Iverson and A.T. Whitney) and in the treatment of cells, items,
and formatting (A.T. Whitney, based on his work on SHARP APL/HP and on
the dialect A reported at the APL89 conference in New York).

E.E. McDonnell of Reuters provided C programs for the
mathematical functions (which applied to complex numbers
as well as to real), D.L. Orth of IBM ported the system
to the IBM RISC System/6000 in time for the APL90 conference,
and L.J. Dickey of the University of Waterloo provided assistance
in porting the system to a number of other computers.

It’s funny, but my recollection is that at the time
I thought I recruited Ken. Whoever recruited whom,
I won a great prize when Ken decided he and I should work together.

The final impetus that got J started was the
one-page interpreter fragment that Arthur wrote,
recorded in Appendix A of An Implementation of J
[29]
and also reproduced in Appendix A below.
My immediate reaction on seeing the page was recoil and puzzlement:
it looked nothing like any C code I had ever seen.
(“Is it even C?”)
However, Ken counselled that I should reserve judgment.
As recounted in An Implementation of J,
it then happened that:

I studied this interpreter for about a week for its organization
and programming style; and on Sunday, August 27, 1989, at about
four o’clock in the afternoon, wrote the first line of
code that became the implementation described in this document.

The name “J” was chosen a few minutes later,
when it became necessary to save the interpreter source file
for the first time.

I consciously designed and built the system
around “Table 2: Parsing Process” in
A Dictionary of APL
[8],
which I had studied carefully and modelled at least two different
ways between 1986 and 1989.
The C data and program structures were designed so that
the parse table in C corresponded as directly as possible
to the parse table in the dictionary.
I set as an objective of being able to show Ken
the C source for the parser, and have him verify that
the syntax being implemented was correct.
We never did carry out the exercise (of Ken reading the C source),
but I reckon I met my objective,
because eventually Ken replaced the table in the dictionary
with the parse table from the C source
[30, section II E].
Other effects of trying to meet the objective were entirely beneficial.

Years after the initial implementation, I happened to re-read
Ken’s APL87 paper APL87
[31].
In retrospect, the paper, in five pages,
prescribed all the essential steps in writing an APL interpreter,
in particular the sections on word formation and parsing.

Ken and I had in mind to implement
A Dictionary of APL
[8]
together with hooks and forks (phrasal forms)
[20].
For years, Ken had struggled to find a way
to write f+g as in calculus,
from the “scalar operators” in Operators and Functions
[5, section 4],
through the “til” operator in
Practical Uses of a Model of APL
[6] and
Rationalized APL
[7, p. 18],
and finally forks.
Forks are defined as follows:

Moreover, (f g p q r) ↔ (f g (p q r)) .
Thus to write f+g as in calculus, one writes f+g in J.
Ken and Eugene McDonnell worked out the details
on the long plane ride back from APL88 in Sydney, Australia,
with Ken coming up with the initial idea on waking up from a nap.

The choice to implement forks was fortuitous and fortunate.
We realized only later
[32]
that forks made tacit expressions (operator expressions) complete
in the following sense:
any sentence involving one or two arguments that
did not use its arguments as an argument to an operator,
can be written tacitly with fork and @: (compose)
and [ (left) and ] (right) and constant functions.
If @: were replaced by the equivalent special
fork [: f g , then a sentence can be written
as an unbroken train (sequence of forks).

Because explicit definition
(the analogue of del-form definitions in APL) was relatively complex,
it was not implemented until some months had elapsed.
As well, the restriction in APL that only nouns (arrays) can be assigned
never made it past the first day, for there was no way other than
by assignment to name verbs, adverbs, and conjunctions
(functions and operators).
Therefore, for some months all verbs were tacit;
that is, all functions were defined as operator expressions.
These circumstances forced us to explore tacit definition extensively.

Meanwhile, Ken was concerned about the usefulness
of forks, and worked hard at finding examples of forks beyond those
in Phrasal Forms
[20].
After a while, it seemed that everything was a fork.
The explanation lies in the proof of completeness for tacit definition
[32]:
if the root (last) function
in a sentence is applied dyadically, then a fork is required to write
the sentence tacitly. Since we wrote tacit definitions exclusively,
it was no wonder that we ran into forks constantly.
As well, we had little trouble expressing computations tacitly
because of the completeness.

Eric Iverson founded Iverson Software Inc. in February 1990
to provide an improved SHARP APL/PC product. It quickly became
obvious that we had shared interests and goals, and in May 1990
Ken and I joined Iverson Software Inc. The company soon
became J only. The name was changed to Jsoftware Inc.
(www.jsoftware.com) in April 2000.

Eric adapted the session manager from SHARP APL/PC
for J in time for the first release.
Over the years, he was responsible for everything that was not
the interpreter proper—the
integrated development environment, the Windows interface,
and all other interfaces—and made
contributions to the language itself,
including locatives, control structures, and memory-mapped files.
Eric also handled product packaging and release details.
Chris Burke joined us in early 1994 and wrote the application libraries,
in particular the plot package, the debugger, the project manager,
and the performance monitor.

Work proceeded rapidly from August 1989. The first public presentation
took place on 1990-02-26 when Ken and I gave a talk complete with
a live demo to the Toronto APLSIG at the Toronto Board of Trade.
The first release of the software was at APL90
[33]
in Copenhagen in August 1990,
when J was made available as shareware to the Software Exchange.
(You can still get this version from various archives.)
The first J conference was held on 1996-06-24 to -25 at the
Koffler Institute of the University of Toronto. There were 123 attendees
and 12 contributed papers in the proceedings
[34].

In working with Ken, I soon realized that
Ken had a flexibility of mind that is breathtaking.
Two examples illustrate this point.

Example 0: For the first few months,
the special APL characters and the ASCII
spelling co-existed in the system.
It was Ken who first suggested that
I should kill off the special APL characters.
I myself resisted for a few weeks longer,
until the situation became too confusing,
for reasons described in J for the APL Programmer
[35, p. 11].

Example 1: It came time to implement (“scan”).
On that day (in the first half of 1990),
during lunch at Josie’s Cafe on Yonge Street, I asked Ken innocently,
“Have you ever wanted to scan something other than reduction?”
The question was not even well-formed,
because the APL paradigm is so powerful
that it usually pushes aside alternative thoughts.
Nevertheless, the discussion that then proceeded
was productive,
and quickly led to the realization that
[35, p. 16]:

Some APL expressions apply reduction implicitly.
For example, APL scan applies its left argument reduction
to successive prefixes of the right argument.
The use of reduction ensured that computations such as sum scan
can be effected by primitive function arguments to the operator,
and that the overall result could be assembled in APL360.

With J’s more permissive assembly rules
(and the use of boxed arrays),
reduction is no longer necessary,
and in many cases, inappropriate.
Therefore in J, if a reduction is required, it must be
specified. Thus +/ in J computes sum scan
and +/. computes suffix sum scan.
The following J example does not use reduction,
and is therefore not readily expressed using APL scan:

   < 'abcdef'
+-+--+---+----+-----+------+
|a|ab|abc|abcd|abcde|abcdef|
+-+--+---+----+-----+------+

Much recent work involved “recognizing” phrases
and implementing them with special code.
The expressive power
of tacit expressions makes this a fruitful approach. For example,
if f is a primitive proposition, then:

are supported by special code.
A primitive proposition is one of the relational atomic verbs
(scalar functions) = ~: < <: > >:
or the verbs E. or e.
(respectively, “substring match” and “member of”;
a legend of the J words used in the text is available in
Appendix B below.) For example:

   'boustrophedonic' (e.i.1:) 'aeiou'     NB. index of first vowel
1
   'boustrophedonic' (e.i:1:) 'aeiou'     NB. index of last  vowel
13

If the target is found near the beginning of the search,
the result is computed instantaneously
(and in time independent of the lengths of the arguments for
atomic verbs f).
Even if the target is found only at the end of the search,
the improvement in time is by a factor of two or more.
In either case the space used is constant
for atomic verbs f .

Another recent development is a port to
the Linux and Windows XP 64-bit operating systems
on the AMD64 and Intel EM64T processors
[36].
J64 has 64-bit integers and a 64-bit address space.

Ken had started to write a companion to the
Abramowitz and Stegun classic,
Handbook of Mathematical Functions
[37].
Such writing was the motivation behind the extended-precision integer
and rational number facilities;
to the same end,
extended-precision floating-point numbers will be also added.
The following examples illustrate extended-precision integers
and rational numbers:

   (+%)/ 10 $ 1
1 2 1.5 1.66667 1.6 1.625 1.61538 1.61905 1.61765 1.61818
   (+%)/ 10 $ 1x
1 2 3r2 5r3 8r5 13r8 21r13 34r21 55r34 89r55
   0j40 ": (+%)/ 100 $ 1x
1.6180339887498948482045868343656381177203

The hook x(+%)y is x plus the reciprocal
of y ,
and so (+%)/ is the continued fraction.
The first phrase computes convergents to the golden ratio phi
in 64-bit IEEE floating-point numbers;
the second computes rational convergents to phi;
and the third computes phi to 40 decimal places.

3. Remembering Ken

Ken and I worked on J in our homes in Toronto,
I in my apartment in the High Park area and Ken
in his apartment on Erskine Avenue and subsequently
in the Manulife Center (a different apartment from the one in 1981,
with an even more spectacular view).
The arrangement placed me uniquely under Ken’s influence.
Oftentimes I found myself at Ken’s house, delivering
the latest J version or working on a computer,
and many times Ken would invite me to
stay for lunch or dinner, explaining that “thou shalt
not muzzle the ox when he treadeth out the corn”.
Little did I imagine in 1981 that the dinner
I had with Ken and Jean then would be the first of many.

It is said that if you keep playing chess with a
grandmaster, your skills can not help but improve.
I had been in almost daily contact with
the master since late 1986, and the following are
a few of the things I have learned.

Credit. When Ken was at Harvard a fellow student
habitually stamped his papers “Copyright”
or “Confidential”.
Howard Aiken, head of the Comp Lab and Ken’s thesis supervisor,
advised, “Don’t worry about people
stealing your ideas. If it’s any good, you’d
have to ram it down their throats!”
(A less picturesque version of this story is found in
[38, p. 240].)

Blame. Ken and I sometimes kidded each other
about whose fault it was when something went wrong.
He complained in jest that I as implementor had
the attitude of “just tell me where to pour the concrete”.
And I, in turn, complained in jest that he as designer
had the attitude that he was never to blame:
If it’s a mistake in the implementation,
then it’s obviously my fault;
and if it’s a mistake in the design,
well then I should have caught it during the implementation.

In truth, I am profoundly grateful to Ken for not complaining
in the times when I failed him, even when I failed him
the same way more than once. I believe that if necessary,
he would have forgiven me for seventy times seven times
(although even I would probably catch on before too long).

Secret to Success. In January 1992,
I was in the final struggles of writing my book
An Implementation of J
[29],
having difficulty and under time pressure.
Around that time, Ken was polishing off several
books and papers, seemingly effortlessly. I asked
him what his secret was. His reply was, basically,
“First, write 500 papers.”

(Ken subsequently gave me some more immediately
useful advice about writing.)

Reading and Writing Carefully.
In the early days I did not have direct access to Ken,
and therefore read his papers carefully. Another example
is Arthur Whitney’s
“one page thing”,
which was the final thing
I studied (for one week) before writing the first line
of source code for J.
Over the years, I have benefitted enormously from
such careful reading.

I later realized that Ken wrote carefully,
in the expectation that what he wrote would be read carefully.
An exemplar of such writing is the description
of “cut” in Rationalized APL
[7, p. 19-20].
It annoyed Ken to no end when accused of being “too terse”,
for example as in “the dictionary is too terse”,
when “terse” means “effectively concise”.

Words. As others have recounted,
Ken was deeply interested in words, their use and their etymology.
He indeed did read the dictionary, and kept a copy of the
American Heritage Dictionary
[39]
(along with other dictionaries)
by his easy chair for ready reference.
He especially encouraged me to consult the section on Indo-European
roots in the back of the AHD,
which makes deep and uncommon connections between words.

Many of Ken’s relatives and friends received
from him the AHD as a present. I myself did not because
I’d already owned one years before I met Ken. In fact,
I gave him the third edition of the AHD as a present.

I think nothing I had ever done impressed Ken quite as much as
when I found the word “rhematic” (meaning, pertaining to the
formation of words), a word he had been searching for for some time.
Thus the phrase “rhematic rules of J”
made its way into the J dictionary
[30].

Books. Before long, Ken and I discovered
that we shared a love of books.
We often recommended reading material to each other.
A sample of our recommendations:

I to Ken: The Language Instinct
by Steven Pinker; Climbing Mount Improbable by Richard Dawkins;
Lincoln at Gettysburg by Garry Wills.
Ken to me: From Dawn to Decadence by Jacques Barzun;
Calvin and Hobbes;
The New York Review of Books.

And, of course, both of us had read The Book of J
[40].

Politics. Unsurprisingly, Ken stood up for what he believed in.
He once spent a few hours in jail after being arrested during a protest
against the Vietnam War. In the same cell was Garry Wills,
the historian and author.

Respect for People. Ken liked to tell
the story of the stoic service agent:
At an airport counter an irate traveller was berating
the service agent over something or other, which the
agent took with stoic forbearance.
After the traveller went on his way,
the next person in line told the agent, “I am amazed at
how well you took that abuse.”
The agent smiled thinly and replied,
“Oh, the gentleman is flying to Chicago,
but his luggage is going to Moscow.”

Ken also suggested, “Be kind to someone trying to make
a living.” I try to remember this every time a taxi or
truck driver cuts me off on the road.

A Questioning and Flexible Mind.
The flexibility of mind that Ken brought to his work (noted above)
was also demonstrated in his everyday life.
For example, it astounded me how often and how thoroughly
Ken rearranged the furniture in his home. His explanation was,
our needs have changed, and we rearranged our surroundings
to meet those needs.

References

Appendix A. Incunabulum

From An Implementation of J
[29],
Appendix A: Incunabulum.

One summer weekend in 1989, Arthur Whitney visited Ken Iverson at
Kiln Farm and produced—on one page and in one
afternoon—an interpreter fragment on the AT&T; 3B1 computer.
I studied this interpreter for about a week for its organization
and programming style; and on Sunday, August 27, 1989, at about
four o’clock in the afternoon, wrote the first line of
code that became the implementation described in this document.

Arthur’s one-page interpreter fragment is as follows:

typedef char C;typedef long I;
typedef struct a{I t,r,d[3],p[2];}*A;
#define P printf
#define R return
#define V1(f) A f(w)A w;
#define V2(f) A f(a,w)A a,w;
#define DO(n,x) {I i=0,_n=(n);for(;i<_n;++i){x;}}
I *ma(n){R(I*)malloc(n*4);}mv(d,s,n)I *d,*s;{DO(n,d[i]=s[i]);}
tr(r,d)I *d;{I z=1;DO(r,z=z*d[i]);R z;}
A ga(t,r,d)I *d;{A z=(A)ma(5+tr(r,d));z->t=t,z->r=r,mv(z->d,d,r);
 R z;}
V1(iota){I n=*w->p;A z=ga(0,1,&n;);DO(n,z->p[i]=i);R z;}
V2(plus){I r=w->r,*d=w->d,n=tr(r,d);A z=ga(0,r,d);
 DO(n,z->p[i]=a->p[i]+w->p[i]);R z;}
V2(from){I r=w->r-1,*d=w->d+1,n=tr(r,d);
 A z=ga(w->t,r,d);mv(z->p,w->p+(n**a->p),n);R z;}
V1(box){A z=ga(1,0,0);*z->p=(I)w;R z;}
V2(cat){I an=tr(a->r,a->d),wn=tr(w->r,w->d),n=an+wn;
 A z=ga(w->t,1,&n;);mv(z->p,a->p,an);mv(z->p+an,w->p,wn);R z;}
V2(find){}
V2(rsh){I r=a->r?*a->d:1,n=tr(r,a->p),wn=tr(w->r,w->d);
 A z=ga(w->t,r,a->p);mv(z->p,w->p,wn=n>wn?wn:n);
 if(n-=wn)mv(z->p+wn,z->p,n);R z;}
V1(sha){A z=ga(0,1,&w-;>r);mv(z->p,w->d,w->r);R z;}
V1(id){R w;}V1(size){A z=ga(0,0,0);*z->p=w->r?*w->d:1;R z;}
pi(i){P("%d ",i);}nl(){P("n");}
pr(w)A w;{I r=w->r,*d=w->d,n=tr(r,d);DO(r,pi(d[i]));nl();
 if(w->t)DO(n,P("< ");pr(w->p[i]))else DO(n,pi(w->p[i]));nl();}
C vt[]="+{~<#,";
A(*vd[])()={0,plus,from,find,0,rsh,cat},
 (*vm[])()={0,id,size,iota,box,sha,0};
I st[26]; qp(a){R  a>='a'&&a;<='z';}qv(a){R a<'a';}
A ex(e)I *e;{I a=*e;
 if(qp(a)){if(e[1]=='=')R st[a-'a']=ex(e+2);a= st[ a-'a'];}
 R qv(a)?(*vm[a])(ex(e+1)):e[1]?(*vd[e[1]])(a,ex(e+2)):(A)a;}
noun(c){A z;if(c<'0'||c>'9')R 0;z=ga(0,0,0);*z->p=c-'0';R z;}
verb(c){I i=0;for(;vt[i];)if(vt[i++]==c)R i;R 0;}
I *wd(s)C *s;{I a,n=strlen(s),*e=ma(n+1);C c;
 DO(n,e[i]=(a=noun(c=s[i]))?a:(a=verb(c))?a:c);e[n]=0;R e;}
main(){C s[99];while(gets(s))pr(ex(wd(s)));}

Appendix B. J Words Used in the Text

Full reference in J Introduction and Dictionary
[30].